package hot_100;

import DynamicProgramming.P5;

/**
 * @author: Darven
 * @createTime: 2025-09-25  19:06
 * @description: TODO
 */
public class P53 {
    public static void main(String[] args) {
        P53 p53 = new P53();
        System.out.println(p53.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }

    public int maxSubArray(int[] nums) {
        // 找到连续数组之和最大
        // 第一想法就是连续的区间，动态规划
        // 从数组中看到[-2,1,-3,4,-1,2,1,-5,4]  会从1重新开始算，从4开始重新算

        int size=nums.length;
        int maxValue = nums[0];
        int[] dp=new int[size];
        dp[0]=nums[0];
        for(int i=1;i<size;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            maxValue=Math.max(maxValue, dp[i]);
        }
        return maxValue;
    }
}
